/*
 * @lc app=leetcode.cn id=46 lang=golang
 *
 * [46] 全排列
 */

// @lc code=start
func permute(nums []int) [][]int {
	n := len(nums)
	ans := make([][]int, 0)

	var backtrace func(index int)
	swap := func(i, j int) {
		nums[i], nums[j] = nums[j], nums[i]
	}
	backtrace = func(index int) {
		if index == n-1 {
			temp := append([]int{}, nums...)
			ans = append(ans, temp)
			return
		}
		for i := index; i < n; i++ {
			swap(i, index)
			backtrace(index + 1)
			swap(i, index)

		}
	}

	backtrace(0)
	return ans
}

// @lc code=end

